/*2、编写一个程序，实现二路归并排序。*/

#include<stdio.h>
#define MAXN 1024
int TOTAL;
void print_array(const int* a,int n){for(int i = 0;i<n;i++)printf("%d ",a[i]);putchar('\n');}


// add_spp[a:c] <- sorted( A[a:b] + A[b+1:c] ) inclusive
void merge_two(int* A,int a,int b,int c,int* add_sp){
    int i,j,k; i = a; j = b+1; k = a;
    while( i <= b &&  j <= c ){
        if( A[i] < A[j] ) add_sp[k++] = A[i++];
        else add_sp[k++] = A[j++];
    }
    while( i<=b )add_sp[k++] = A[i++];
    while( j<=c )add_sp[k++] = A[j++];
    // printf("[Merge [%2d:%2d][%2d:%2d] ]",a,b,b+1,c);print_array(add_sp,TOTAL);
}

// merge each pair of t-length section in A and copy to B
void merge_pass(int* A,int* B,int n,int t){
    int i,j,k;
    i = 0; j = 0;
    while(i<n){
        j = i + t - 1;
        k = i + t + t - 1;
        if(j>n-1)j=n-1;
        if(k>n-1)k=n-1;
        merge_two(A,i,j,k,B);
        i = i + t + t;
    }
}

void merge_sort(int* a,int n,int* additional_space){
    int t = 1;
    while( t < n ){
        merge_pass(a,additional_space,n,t); t *= 2;
        merge_pass(additional_space,a,n,t); t *= 2;
    }
}

int main(){
    int n,i;
    int A[MAXN];
    int S[MAXN];
    scanf("%d",&n);
    TOTAL = n;
    for(i=0;i<n;i++)scanf("%d",A+i);
    merge_sort(A,n,S);
    for(i=0;i<n;i++)printf("%d ",A[i]);
    return 0;
}